package 回溯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 组合总和 {
   static class Solution{
        public List<List<Integer>> combinationSum(int[] candidates ,int target){
            ArrayList<List<Integer>> res = new ArrayList<>();
            //先将candidates排序
            Arrays.sort(candidates);
            backtracking(res,new ArrayList<>(),candidates,target,0,0);
            return res;

        }

        private void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target,int sum, int idx) {
                    if (sum == target){
                        res.add(new ArrayList<>(path));
                        return;
                    }
            for (int i = idx; i < candidates.length; i++) {
                if (sum + candidates[i] >target) break; //这里应该是不满足的话 退出的是当前的那个递归
                path.add(candidates[i]);
                backtracking(res,path,candidates,target,sum+candidates[i],i); //我觉得传入i的原因是 比如你for到【2，3，5】的3的时候不应该回到2了
                                                                                    //这就会导致与之前2的搜索重叠了
                path.remove(path.size()-1);// 回溯，移除路径 path 最后一个元素
            }
        }
    }
}
